class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p: return not s
        # 第一个字母是否匹配
        first_match = bool(s and p[0] in {s[0],'.'})
        # 如果 p 第二个字母是 *
        if len(p) >= 2 and p[1] == "*":
            # *匹配空，模式串往后走两个，否则字符串往后走一个，字符串走没了就是匹配空，往前走两个，用or两个有一个true就是true
            return self.isMatch(s, p[2:]) or \
            first_match and self.isMatch(s[1:], p)
        else:
            return first_match and self.isMatch(s[1:], p[1:])
'''
魔法打败魔法
'''
# ans = re.fullmatch(p, s)
#         return ans != None

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p: return not s
        potMatch = bool(s and p[0] in {s[0],'.'})
        if len(p) >=2 and p[1] == '*':
            return potMatch and self.isMatch(s[1:],p) or self.isMatch(s,p[2:])
        else:
            return potMatch and self.isMatch(s[1:],p[1:])

'''
dp版本
'''
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # i,j 主串，p通配串，+1 得到空的行的一行，也就是两个第0行
        m, n = len(s) + 1, len(p) + 1
        # 边界条件，一个串结束了另一个没结束或者s为空且p不为空
        if not p: return not s
        # if not s and len(p) == 1: return False
        # m 行 n 列，行对用i列对应j
        dp = [[False for _ in range(n)] for _ in range(m)] # 空通配串和没有遍历到的全都都不匹配
        # 初始化
        dp[0][0] = True # 空字符串与空字符串相匹配
        # 空主串，也就是第零行，和非空通配串，通配串有一个*可以消除前一个，看是否能消除到00，消除的到就是True
        # 否则就是False
        for j in range(2, n):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]
        # dp，子串和匹配都非空
        for i in range(1,m):
            for j in range(1,n):
                if p[j-1] == '*':
                    if p[j - 2] == s[i-1] or p[j - 2] == '.':
                        dp[i][j] = dp[i-1][j] | dp[i][j-2]
                    else:
                        dp[i][j] = dp[i][j-2]
                elif p[j-1] == '.' or p[j-1] == s[i-1]:
                    dp[i][j] = dp[i-1][j-1]
                # 默认就是false啊
                # else:
                #     dp[i][j] = False
        return dp[m-1][n-1]